package com.haidechizi.backup.sort;

import java.util.Arrays;

/**
 * c插入排序
 */
public class InsertSort {


    public static void main(String[] args) {
        int[] arr = new int[]{8, 3, 5, 0, 1, 4, 6};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     *
     * 数组的钱i个数据都是拍完徐的数字
     *
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {

        // 只有一个数时，已经是排好序的，因此从i=1开始
        for (int i= 1; i< arr.length ; i++) {
            // 记录当前需要排序的值
            int temp  = arr[i];
            // 记录下标
            int j;
            // 对前i-1个数字进行排序,只有当第j个数大于temp时，才巫妖排序
            for ( j = i-1;j >=0 && arr[j] > temp; j--) {
                // 当第j个数大于temp时，将第j个后移到j+1的位置上
                arr[j+1] = arr[j];

            }
            arr[j+1] = temp;
        }


    }
}
